package goleetcode

import "container/heap"

func minDays(n int) int {
	q := &PriorityQueru{Pair{0, n}}
	visited := make(map[int]bool)
	ans := 0
	for true {
		p := heap.Pop(q).(Pair)
		days, rest := p.first, p.second
		if visited[rest] {
			continue
		}
		visited[rest] = true
		if rest == 1 {
			ans = days + 1
			break
		}
		heap.Push(q, Pair{days + rest%2 + 1, rest / 2})
		heap.Push(q, Pair{days + rest%3 + 1, rest / 3})
	}
	return ans
}

type Pair struct {
	first  int
	second int
}

type PriorityQueru []Pair

func (pq PriorityQueru) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
}

func (pq PriorityQueru) Len() int {
	return len(pq)
}

func (pq PriorityQueru) Less(i, j int) bool {
	return pq[i].first < pq[j].first
}

func (pq *PriorityQueru) Push(x interface{}) {
	*pq = append(*pq, x.(Pair))
}

func (pq *PriorityQueru) Pop() interface{} {
	n := len(*pq)
	x := (*pq)[n-1]
	*pq = (*pq)[:n-1]
	return x
}
